In software it is frequently necessary for one part of a program to make reference to a program element such as a data structure that was constructed by some other portion of the program. Such elements are commonly referred to as objects. The means commonly employed for referring to an object is to use a pointer to the object. A problem arises when the object being pointed to is destroyed and a subsequent attempt is made to use the pointer to access the object. This usually leads to a fatal program error. This is commonly referred to as the dangling pointer problem.
One approach to solving the dangling pointer problem is to count the number of references to an object. Since objects can not be safely destroyed until all references to them are removed, object destruction is postponed until the pointer count reaches zero. This presents a problem when circular references exist. In FIG. 1, objects A and B have pointers to each other and some other global pointer (somewhere else in the program) refers to object A. It can be assumed that the pointers shown are all of the existing pointers to A and B. If the global pointer is removed (either destroyed or made to point to another object), objects A and B remain inaccessible from the rest of the program. However they cannot be destroyed, since each has one remaining pointer to it. Objects A and B are garbage as far as the rest of the program is concerned. The problem of identifying them as garbage, and removing them is known as the garbage collection problem.
To deal with the garbage collection problem, previous pointer counting schemes have required the application programmer to explicitly identify situations such as just described, and to write code that explicitly removes some pointers, such as the pointer from B to A in FIG. 1. After the removal of these pointers, some objects (A in this example) will have no remaining pointers and can be destroyed. In the process of destruction, the pointers that these objects have to other objects are also destroyed (in this example, the pointer from A to B) leaving others objects (B) with no remaining pointers. The process continues until all isolated objects have been destroyed. The problem with this approach is not the writing of the code that dismantles the pointers but is determining when to call the code. The programmer must determine when each segment becomes isolated.
The garbage collection problem has a serious effect on the software development process. Despite continuing advances in language and software technology, the proper management of memory continues to constitute a large portion of the overall effort required to develop software systems. In the popular C language, the simplicity of malloc ( ) and free ( ) has great appeal. However, this simplicity does have its costs. It is simply too easy to prematurely free memory and then attempt to reference that memory with a dangling pointer, or to fail to free memory altogether, creating a memory leak. Unfortunately, it is usually very hard to locate and fix these types of errors once they have been made. They are usually the types of errors that can remain undetected despite testing, possibly leading to dangerous and expensive failures of software in the field.
From the programmer's point of view, the best remedy to these problems is automatic garbage collection. In languages that support automatic garbage collection, memory management becomes trivial: one simply allocates an object whenever needed, with no worry about deallocating it. Most automatic garbage collection schemes have depended upon exhaustive searches through an application's data space for any and all references to objects. However, another mechanism is needed because the processing requirements of such exhaustive searches makes this technique too inefficient for most current C and C++ applications.